#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-08-12 9:30 上午
# @Author  : yangdy
# @File    : 2020-08-12.133.克隆图
# @Software: PyCharmCE
"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = []):
        self.val = val
        self.neighbors = neighbors
"""


class Node:
    def __init__(self, val=0, neighbors=[]):
        self.val = val
        self.neighbors = neighbors


class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        # 1. python copy
        # import copy
        # return copy.deepcopy(node)
        # 2. dfs
        if not node:
            return None
        mm = {}

        def dfs(nd):
            if not nd:
                return None
            if mm.get(nd.val):
                return mm[nd.val]
            x = Node(nd.val)
            mm[nd.val] = x
            for y in nd.neighbors:
                x.neighbors.append(dfs(y))
            return x

        return dfs(node)


questions = [
    (),
]

